{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Contiguous Sequence LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #divide-and-conquer #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #分治 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxSubArray"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #连续数列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个整数数组，找出总和最大的连续数列，并返回总和。</p>\n",
    "\n",
    "<p><strong>示例：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong> [-2,1,-3,4,-1,2,1,-5,4]\n",
    "<strong>输出：</strong> 6\n",
    "<strong>解释：</strong> 连续子数组 [4,-1,2,1] 的和最大，为 6。\n",
    "</pre>\n",
    "\n",
    "<p><strong>进阶：</strong></p>\n",
    "\n",
    "<p>如果你已经实现复杂度为 O(<em>n</em>) 的解法，尝试使用更为精妙的分治法求解。</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [contiguous-sequence-lcci](https://leetcode.cn/problems/contiguous-sequence-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [contiguous-sequence-lcci](https://leetcode.cn/problems/contiguous-sequence-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[-2,1,-3,4,-1,2,1,-5,4]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        cur=res=float('-inf')#表示正负无穷\n",
    "        for num in nums:\n",
    "            cur=max(cur+num,num)\n",
    "            res=max(res,cur)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        pre = 0\n",
    "        ans = -inf\n",
    "        for num in nums:\n",
    "            if pre >= 0:\n",
    "                pre += num\n",
    "            else:\n",
    "                pre = num\n",
    "            ans = max(ans,pre)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 0:\n",
    "            return 0\n",
    "        if len(nums) == 1:\n",
    "            return nums[0]       \n",
    "        tsum = 0\n",
    "        for i in nums:\n",
    "            tsum += i\n",
    "        left = [0] * (len(nums)+1)\n",
    "        leftmin = [0] * (len(nums)+1)\n",
    "        right = [0] * (len(nums)+1)\n",
    "        rightmin = [0] * (len(nums)+1)\n",
    "        for i in range(1, len(nums)+1):\n",
    "            left[i] = left[i-1] + nums[i-1]\n",
    "            if nums[i-1] < 0:\n",
    "                leftmin[i] = min(left[i],leftmin[i-1])\n",
    "            else:\n",
    "                leftmin[i] = leftmin[i-1]\n",
    "            right[-i-1] = right[-i] + nums[-i]\n",
    "            if nums[-i] < 0:\n",
    "                rightmin[-i-1] = min(rightmin[-i],right[-i-1])\n",
    "            else:\n",
    "                rightmin[-i-1] = rightmin[-i]\n",
    "        mn = 0\n",
    "        ii = 0\n",
    "        for i in range(0,len(nums)):\n",
    "            leftplusrightmin = leftmin[i] + rightmin[i+1]\n",
    "            if leftplusrightmin < mn:\n",
    "                mn = leftplusrightmin\n",
    "                ii = i\n",
    "        print(left)\n",
    "        print(leftmin)\n",
    "        print(right)\n",
    "        print(rightmin)\n",
    "        print(tsum, ii, mn)\n",
    "        return tsum - mn\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        res = nums[0]\n",
    "        tmp = nums[0]\n",
    "        for i in nums[1:]:\n",
    "            tmp = max(i, i + tmp)\n",
    "            res = max(res, tmp)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        ans = -inf\n",
    "        curr = -inf\n",
    "        for n in nums:\n",
    "            curr = max(curr + n, n)\n",
    "            ans = max(ans, curr)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        cur_sum = max_sum = nums[0]\n",
    "        for num in nums[1:]:\n",
    "            cur_sum = max(num, cur_sum + num)\n",
    "            max_sum = max(max_sum, cur_sum)\n",
    "        return max_sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        pre, maxAns = 0, nums[0]\n",
    "        for i in range(len(nums)):\n",
    "            pre = max(pre + nums[i], nums[i])\n",
    "            maxAns = max(maxAns, pre)\n",
    "        return maxAns"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        ret = -inf\n",
    "        summary = -inf\n",
    "\n",
    "        for num in nums:\n",
    "            summary = max(summary + num, num)\n",
    "            ret = max(ret, summary)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        cur_sum = max_sum = nums[0]\n",
    "        for num in nums[1:]:\n",
    "            cur_sum = max(num, cur_sum + num)\n",
    "            max_sum = max(max_sum, cur_sum)\n",
    "        return max_sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        i=0\n",
    "        count=0\n",
    "        ma=-0xffffffff\n",
    "        while(i<len(nums)):\n",
    "            count+=nums[i]\n",
    "            if  count>ma:\n",
    "                ma=count\n",
    "            if count<0:\n",
    "                count=0\n",
    "            i+=1\n",
    "        return ma"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        res = nums[0]\n",
    "        maxnum = res\n",
    "        for n in nums[1:]:\n",
    "            res = max(res+n,n)\n",
    "            if maxnum < res:\n",
    "                maxnum = res\n",
    "        return maxnum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        if nums == []:\n",
    "            return 0\n",
    "        max = nums[0]\n",
    "        now = nums[0]\n",
    "        for i in range(1,len(nums)):\n",
    "            if now<0:\n",
    "                now = nums[i]\n",
    "            else:\n",
    "                now += nums[i]\n",
    "            if now>max:\n",
    "                max = now\n",
    "        return max"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        maxsum,sum=float('-inf'),float('-inf')\n",
    "        for i in nums:\n",
    "            sum=max(sum+i,i)\n",
    "            maxsum=max(sum,maxsum)\n",
    "        return maxsum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        b=nums\n",
    "        r=[0 for i in range(len(b))]\n",
    "        r[0]=b[0]\n",
    "        sum=b[0]\n",
    "        for i in range(1,len(b)):\n",
    "            sum=max(b[i],sum+b[i])\n",
    "            if sum>r[i-1]:\n",
    "                r[i]=sum\n",
    "            else:\n",
    "                r[i]=r[i-1]\n",
    "        return r[len(b)-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        # 定义max_sum: 表示全局最大子序列和\n",
    "        # 定义current_sum: 表示以当前元素为结尾的最大子序列和\n",
    "        max_sum = current_sum = nums[0]\n",
    "\n",
    "        for i in range(1, len(nums)):\n",
    "            current_sum = max(nums[i], current_sum + nums[i])\n",
    "            max_sum = max(max_sum, current_sum)\n",
    "\n",
    "        return max_sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        sm = nums[0]\n",
    "        mx = nums[0]\n",
    "        for i in range(1, len(nums)):\n",
    "            sm = max(sm + nums[i], nums[i])\n",
    "            mx = max(mx, sm)\n",
    "        return mx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        m = len(nums)\n",
    "        res = nums[0]\n",
    "        total = 0\n",
    "        for i in range(m):\n",
    "            total += nums[i]\n",
    "            if total < nums[i]:\n",
    "                total = nums[i]\n",
    "            res = max(res, total)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        sum=maxsum=float('-inf')\n",
    "        for i in range(len(nums)):\n",
    "            sum = max(sum+nums[i],nums[i])\n",
    "            maxsum = max(sum,maxsum)\n",
    "        return maxsum\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''cclass Solution:\n",
    "    def maxSubArray(self, nums):\n",
    "        ret, lg = nums[0], len(nums)\n",
    "        for i in range(len(nums)):\n",
    "            cnt = 0\n",
    "            for j in range(i, len(nums)):\n",
    "                cnt += nums[j]\n",
    "                ret = max(cnt, ret)\n",
    "                if cnt <= 0:\n",
    "                    break\n",
    "        return ret'''\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums):\n",
    "        cnt, ret = 0, nums[0]\n",
    "        for num in nums:\n",
    "            cnt = max(num, cnt + num)\n",
    "            ret = max(ret, cnt)\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        l=r=0\n",
    "        sum=0\n",
    "        maxres=0\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]>0:\n",
    "                l=r=i\n",
    "                break\n",
    "        sum=nums[l]\n",
    "        if sum<0:sum=0\n",
    "        maxres=nums[l]\n",
    "        for i in range(l+1,len(nums)):\n",
    "            sum+=nums[i]\n",
    "            maxres=max(maxres,sum)\n",
    "            if sum<0:sum=0\n",
    "            \n",
    "            \n",
    "        return maxres"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums):\n",
    "        cnt, ret = 0, nums[0]\n",
    "        for num in nums:\n",
    "            cnt = max(num, cnt + num)\n",
    "            ret = max(ret, cnt)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums):\n",
    "        cnt, ret = 0, nums[0]\n",
    "        for num in nums:\n",
    "            cnt = max(num, cnt + num)\n",
    "            ret = max(ret, cnt)\n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        res = nums[0]\n",
    "        tmp = float('-inf')\n",
    "        length = len(nums)\n",
    "\n",
    "        if length <= 1:\n",
    "            return res\n",
    "\n",
    "        start, end = 1, length\n",
    "        ans = nums[0]\n",
    "        while start < end:\n",
    "            ans = max(nums[start], ans)\n",
    "            if nums[start] > 0:\n",
    "                if res < 0:\n",
    "                    res = 0\n",
    "\n",
    "            res += nums[start]\n",
    "            if nums[start] > 0:\n",
    "                if res > 0:\n",
    "                    ans = max(res, tmp, ans)\n",
    "                    tmp = res\n",
    "            start += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums):\n",
    "        cnt, ret = 0, nums[0]\n",
    "        for num in nums:\n",
    "            cnt = max(num, cnt + num)\n",
    "            ret = max(ret, cnt)\n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "\n",
    "        global_max = cur = nums[0]\n",
    "\n",
    "        for i in range(1, len(nums)):\n",
    "            cur = max(nums[i], cur + nums[i])\n",
    "            global_max = max(cur, global_max)\n",
    "            \n",
    "        return global_max"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        res = max(nums)\n",
    "        tmp = 0\n",
    "        for i in range(len(nums)):\n",
    "            res = max(tmp + nums[i], res)\n",
    "            tmp = max(0, tmp + nums[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 0:\n",
    "            return 0\n",
    "        res = nums[0]\n",
    "        cur = nums[0]\n",
    "        for i in range(1,len(nums)):\n",
    "            if cur < 0:\n",
    "                cur = nums[i]\n",
    "            else:\n",
    "                cur += nums[i]\n",
    "            res = max(res,cur)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = nums[0]\n",
    "        dp = [0] * n\n",
    "        dp[0] = nums[0]\n",
    "        for i in range(1, n):\n",
    "            if dp[i-1] > 0:\n",
    "                dp[i] = dp[i-1] + nums[i]\n",
    "            else:\n",
    "                dp[i] = nums[i]\n",
    "            ans = max(ans, dp[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        maxsum, sum = float('-inf'), float('-inf')\n",
    "        for i in nums:\n",
    "            sum = max(sum + i, i)\n",
    "            maxsum = max(sum, maxsum)\n",
    "        return maxsum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        def get(a,l,r):\n",
    "            if l==r: return a[l],a[l],a[l],a[l]\n",
    "            L,R = get(a,l,(l+r)//2),get(a,(l+r)//2+1,r)\n",
    "            return max(L[0],L[3]+R[0]),max(R[1],R[3]+L[1]),max(L[2],R[2],L[1]+R[0]),L[3]+R[3]\n",
    "        return get(nums,0,len(nums)-1)[2]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 0:\n",
    "            return 0\n",
    "            \n",
    "        dp = [0 for _ in range(len(nums))]\n",
    "\n",
    "        dp[0] = nums[0]\n",
    "        ans = dp[0]\n",
    "        for i in range(1, len(nums)):\n",
    "            dp[i] = max(dp[i-1] + nums[i], nums[i])\n",
    "            if dp[i] > ans:\n",
    "                ans = dp[i]\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        m = len(nums)\n",
    "        dp = [0] * m\n",
    "        dp[0] = nums[0]\n",
    "        for i in range(1, m):\n",
    "            dp[i] = max(nums[i], dp[i - 1] + nums[i])\n",
    "\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 0:\n",
    "            return 0\n",
    "        return self.sum(nums, 0, len(nums)-1)[2]\n",
    "    \n",
    "    def sum(self, nums, i, j) -> Tuple[int, int, int, int]:\n",
    "        if i == j:\n",
    "            return [nums[i]]*4\n",
    "        mid = (i+j) // 2\n",
    "        l1, l2, l3, l4 = self.sum(nums, i, mid)\n",
    "        r1, r2, r3, r4 = self.sum(nums, mid+1, j)\n",
    "        c1 = max(l1, l4+r1)\n",
    "        c2 = max(r2, l2+r4)\n",
    "        c3 = max(l3, r3, l2+r1)\n",
    "        c4 = l4 + r4\n",
    "        return c1, c2, c3, c4\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        pre, res = 0, nums[0]\n",
    "        for i in nums:\n",
    "            pre = max(pre + i, i)\n",
    "            res = max(res, pre)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        # 动态规划\n",
    "        # n = len(nums)\n",
    "        # res = nums[0]\n",
    "        # ans = res\n",
    "        # for i in range(1,n):\n",
    "        #     res = max(res+nums[i],nums[i])\n",
    "        #     ans = max(res,ans)\n",
    "        # return ans\n",
    "\n",
    "        # 分治\n",
    "        def func(nums,l,r):\n",
    "            if l==r:\n",
    "                return nums[l],nums[l],nums[l],nums[l]\n",
    "            mid = (l+r)//2\n",
    "            left = func(nums,l,mid)\n",
    "            right = func(nums,mid+1,r)\n",
    "            return max(left[0],left[-1],left[-1]+right[0]),max(right[1],right[-1],right[-1]+left[1]),max(left[2],right[2],left[1]+right[0]),left[-1]+right[-1]\n",
    "        return func(nums,0,len(nums)-1)[2]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        dp=[]\n",
    "        dp.append(nums[0])\n",
    "        for i in range(1,len(nums)):\n",
    "            dp.append(max(dp[i-1]+nums[i],nums[i]))\n",
    "        \n",
    "        return max(dp)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef maxSubArray(self, nums: List[int]) -> int:\n",
    "\t\tcurrent, max_count = 0, nums[0]\n",
    "\t\tfor num in nums:\n",
    "\t\t\tcurrent = max(current + num, num)\n",
    "\t\t\tmax_count = max(current, max_count)\n",
    "\t\treturn max_count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        dp=[0]*len(nums)\n",
    "        dp[0]=nums[0]\n",
    "        for i in range(1,len(nums)):\n",
    "            dp[i]=max(dp[i-1]+nums[i],nums[i])\n",
    "        return max(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        # maxnum = nums[0]\n",
    "        # for i in range(1, len(nums)):\n",
    "        #     if nums[i] + nums[i - 1] > nums[i]:\n",
    "        #         nums[i] += nums[i - 1]\n",
    "        #     if nums[i] > maxnum:\n",
    "        #         maxnum = nums[i]\n",
    "        # return maxnum\n",
    "        dp = [0] * len(nums)\n",
    "        dp[0] = nums[0]\n",
    "        for i in range(1, len(nums)):\n",
    "            dp[i] = max(dp[i-1] + nums[i], nums[i])\n",
    "        return max(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        dp=[nums[0]]\n",
    "        for i in range(1,len(nums)):\n",
    "            if dp[-1]>0:\n",
    "                dp.append(dp[-1]+nums[i])\n",
    "            else:\n",
    "                dp.append(nums[i])\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        # 动态规划\n",
    "        # n = len(nums)\n",
    "        # res = nums[0]\n",
    "        # ans = res\n",
    "        # for i in range(1,n):\n",
    "        #     res = max(res+nums[i],nums[i])\n",
    "        #     ans = max(res,ans)\n",
    "        # return ans\n",
    "\n",
    "        # 分治\n",
    "        def func(nums,l,r):\n",
    "            if l==r:\n",
    "                return nums[l],nums[l],nums[l],nums[l]\n",
    "            mid = (l+r)//2\n",
    "            left = func(nums,l,mid)\n",
    "            right = func(nums,mid+1,r)\n",
    "            return max(left[0],left[-1]+right[0]),max(right[1],right[-1]+left[1]),max(left[2],right[2],left[1]+right[0]),left[-1]+right[-1]\n",
    "        return func(nums,0,len(nums)-1)[2]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums):\n",
    "        max1 = nums[0]\n",
    "        max2 = nums[0]\n",
    "        for i in nums[1:len(nums)]:\n",
    "            print(i)\n",
    "            max1 = max(i,max1+i)\n",
    "            max2 = max(max1,max2)\n",
    "        return max2\n",
    "\n",
    "\n",
    "\n",
    " \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        if nums[-1] > 0:\n",
    "            for i in range(1,len(nums)):\n",
    "                nums[i] += max(nums[i-1],0)\n",
    "        else:\n",
    "            for i in range(1,len(nums)-1):\n",
    "                nums[i] += max(nums[i-1],0)\n",
    "        return max(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        dp = [0] * len(nums)\n",
    "        dp[0] = nums[0]\n",
    "        max_res = dp[0]\n",
    "        for i in range(1, len(nums)):\n",
    "            dp[i] = max(nums[i], dp[i - 1] + nums[i])\n",
    "            if dp[i] > max_res:\n",
    "                max_res = dp[i]\n",
    "            #print(dp)\n",
    "        return max_res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        for i in range(1,len(nums)):\n",
    "            nums[i] += max(nums[i-1],0)\n",
    "        return max(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        maxans = nums[0]\n",
    "        for i in nums:\n",
    "            ans+=i\n",
    "            maxans = max(maxans,ans)\n",
    "            ans = max(0,ans)\n",
    "        return maxans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        dp = [0] * len(nums)\n",
    "        dp[0] = nums[0]\n",
    "        for i in range(1,len(nums)):\n",
    "            dp[i] = max(dp[i-1]+nums[i],nums[i])\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        # if n==0:return 0\n",
    "        res = 0\n",
    "        dp = [0]*n\n",
    "        dp[0] = nums[0]\n",
    "        for i in range(1,n):\n",
    "            dp[i] = max(dp[i-1]+nums[i],nums[i])\n",
    "        return max(dp)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        maxnum = nums[0]\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] + nums[i - 1] > nums[i]:\n",
    "                nums[i] += nums[i - 1]\n",
    "            if nums[i] > maxnum:\n",
    "                maxnum = nums[i]\n",
    "        return maxnum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 1:\n",
    "            return nums[0]\n",
    "        n = len(nums)\n",
    "        dp = [0] * n\n",
    "        dp[0] = nums[0]\n",
    "        \n",
    "        for i in range(n):\n",
    "            dp[i] = max(nums[i], dp[i - 1] + nums[i])\n",
    "\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    class Sub_Status:\n",
    "        def __init__(self, l_sum: int, r_sum: int, m_sum: int, i_sum: int):\n",
    "            \"\"\"\n",
    "            :param l_sum: 表示区间[l, r]内以l为左端点的最大子段和\n",
    "            :param r_sum: 表示区间[l, r]内以r为右端点的最大子段和\n",
    "            :param m_sum: 表示区间[l, r]内的最大子段和\n",
    "            :param i_sum: 表示区间[l, r]的区间和\n",
    "            \"\"\"\n",
    "            self.l_sum = l_sum\n",
    "            self.r_sum = r_sum\n",
    "            self.m_sum = m_sum\n",
    "            self.i_sum = i_sum\n",
    "\n",
    "    def get_sub_sum(self, nums: List[int], l: int, r: int):\n",
    "        if r == l:\n",
    "            status = self.Sub_Status(nums[l], nums[l], nums[l], nums[l])\n",
    "        else:\n",
    "            mid = (l + r) // 2\n",
    "            l_status = self.get_sub_sum(nums, l, mid)\n",
    "            r_status = self.get_sub_sum(nums, mid + 1, r)\n",
    "            l_sum = max(l_status.l_sum, l_status.i_sum + r_status.l_sum)\n",
    "            r_sum = max(r_status.r_sum, r_status.i_sum + l_status.r_sum)\n",
    "            m_sum = max(l_status.m_sum, r_status.m_sum, l_status.r_sum + r_status.l_sum)\n",
    "            i_sum = l_status.i_sum + r_status.i_sum\n",
    "            status = self.Sub_Status(l_sum, r_sum, m_sum, i_sum)\n",
    "        return status\n",
    "\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        分治算法\n",
    "        \"\"\"\n",
    "        status = self.get_sub_sum(nums, 0, len(nums)-1)\n",
    "        return status.m_sum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        for i in range(1,n):\n",
    "            nums[i] = max(nums[i-1] + nums[i],nums[i])\n",
    "        return max(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        maxsum, sum = float('-inf'), float('-inf')\n",
    "        for i in nums:\n",
    "            sum = max(sum + i, i)\n",
    "            maxsum = max(sum, maxsum)\n",
    "        return maxsum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        dp = [0] * len(nums)\n",
    "        dp[0] = nums[0]  #初始化\n",
    "        for i in range(1,len(nums)):\n",
    "            dp[i] = max(dp[i-1]+nums[i],nums[i]) #假设第i个值+i个值的总和，还没第i个值大，那以前的数九丢弃掉\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [0 for _ in range(n+1)]\n",
    "        dp[0] = float('-inf')\n",
    "        for i in range(1, n+1):\n",
    "            dp[i] = max(nums[i-1], dp[i-1] + nums[i-1])\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        if len(nums) < 2:\n",
    "            return nums[0]\n",
    "\n",
    "        dp = [0] * len(nums)\n",
    "\n",
    "        dp[0] = nums[0]\n",
    "        res = dp[0]\n",
    "        \n",
    "        for i in range(1, len(nums)):\n",
    "            dp[i] = max(nums[i], dp[i-1] + nums[i])\n",
    "            res = max(res, dp[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        dp = [0]*len(nums)\n",
    "        dp[0] = nums[0]\n",
    "        for i in range(1,len(nums)):\n",
    "            dp[i] = max(dp[i-1]+nums[i],nums[i])\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        #dp[i]表示到i位置的最大和\n",
    "        #dp[i]=max(nums[i],dp[i-1]+nums[i])\n",
    "        dp=[0]*len(nums)\n",
    "        dp[0]=nums[0]\n",
    "        for i in range(1,len(nums)):\n",
    "            dp[i]=max(nums[i],dp[i-1]+nums[i])\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        dp=[0]*len(nums)\n",
    "        dp[0]=nums[0]\n",
    "        for i in range(1,len(nums)):\n",
    "            dp[i]=max(dp[i-1]+nums[i],nums[i])\n",
    "        return max(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        if nums == []:\n",
    "            return 0\n",
    "        for i in range(1, len(nums)):\n",
    "            nums[i] = max(nums[i] + nums[i-1], nums[i])\n",
    "        return max(nums)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [0] * n\n",
    "        dp[0] = nums[0]\n",
    "        for k in range(1,n):\n",
    "            dp[k] = max(dp[k-1] + nums[k],nums[k])\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        for i in range(1,n):\n",
    "            nums[i] = max(nums[i-1] + nums[i],nums[i])\n",
    "        return max(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        for i in range(1,len(nums)):\n",
    "            nums[i] += max(nums[i-1],0)\n",
    "        return max(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        动态规划算法\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        dp = [0] * n\n",
    "        dp[0] = nums[0]\n",
    "        for i in range(1, n):\n",
    "            dp[i] = max(dp[i - 1] + nums[i], nums[i])\n",
    "        return max(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        dp = [0] * len(nums)\n",
    "\n",
    "        dp[0] = nums[0]\n",
    "        res = dp[0]\n",
    "\n",
    "        for i in range(1, len(nums)):\n",
    "            dp[i] = max(nums[i], dp[i-1] + nums[i])\n",
    "            res = max(res, dp[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        memorize = [0]*n\n",
    "        memorize[0] = nums[0]\n",
    "        for i in range(1,n):\n",
    "            memorize[i] = max(memorize[i-1]+nums[i],nums[i])\n",
    "        return max(memorize)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        mp = [0] * n \n",
    "        if n == 0:\n",
    "            return 0\n",
    "        mp[0] = nums[0]\n",
    "        for i in range(1,n):\n",
    "            mp[i] = max(mp[i-1] + nums[i],nums[i])\n",
    "        return max(mp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        dp = [0] * len(nums)\n",
    "        dp[0] = nums[0]\n",
    "\n",
    "        for i in range(1,len(nums)):\n",
    "            dp[i] = max(dp[i-1]+nums[i],nums[i])\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        maxs = nums[0]\n",
    "\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i - 1] > 0:\n",
    "                nums[i] += nums[i - 1]\n",
    "            maxs = max(maxs, nums[i])\n",
    "            \n",
    "        return maxs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        max_val = nums[0]\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] + nums[i - 1] > nums[i]:\n",
    "                nums[i] += nums[i-1]\n",
    "            max_val = max(nums[i], max_val)\n",
    "        return max_val\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return float('-inf')\n",
    "        dp=[0]*len(nums)\n",
    "        dp[0]=nums[0]\n",
    "        ret=nums[0]\n",
    "        for i in range(1,len(nums)):\n",
    "            dp[i]=max(dp[i-1]+nums[i], nums[i])\n",
    "            ret=max(ret, dp[i])\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        dp=[0]*len(nums)\n",
    "        dp[0]=nums[0]\n",
    "        for i in range(1,len(nums)):\n",
    "            dp[i]=max(dp[i-1]+nums[i],nums[i])\n",
    "        return max(dp)\n",
    "\n",
    "#关键就是状态转移方程比较难写\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        nn = len(nums)\n",
    "        res = [0 for i in range(0, nn)]\n",
    "        res[0] = nums[0]\n",
    "        r = nums[0]\n",
    "\n",
    "        for i in range(1, nn):\n",
    "            if res[i-1] <= 0:\n",
    "                res[i] = nums[i]\n",
    "            else:\n",
    "                res[i] = res[i-1] + nums[i]\n",
    "            r = max(r, res[i])\n",
    "        \n",
    "        return r"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
